package P148_排序链表;

//nlog(n)的链表排序
//考虑用归并排序
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    public void pp(){
        ListNode x = this;
        while(x != null){
            System.out.println(x.val);
            x = x.next;
        }
    }

    @Override
    public String toString() {
        String x = "";
        ListNode b = this;
        while(b != null){
            x+=b.val+"->";
            b=b.next;
        }
        return x.substring(0,x.length()-2);
    }
}

public class Solution {
    //保证传入的node1.val <= node2.val
    //Deprecated, 空间不满足
    public ListNode merge(ListNode node1, ListNode node2){
        //自动以node1作为起点，因为保证了他的值小
        //现在就是将node2整条插入到node1中
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = node1;
        ListNode preNode1 = dummyNode;
        ListNode cur;
        while(preNode1.next != null && node2!= null){
            if(preNode1.next.val > node2.val){
                int tmp = preNode1.next.val;
                cur = preNode1.next;
                preNode1.next = node2;

                //node1 : 1->3->9->10  node2: 4->5->6->12
                //node2中究竟要过来几个还不好说，需要遍历node2

                //TODO 这里每次都需要新建的preNode2，空间需求不是O(1)而是O(N)了
                ListNode preNode2 = new ListNode(-1);
                preNode2.next = node2;
                while(preNode2.next != null && tmp > preNode2.next.val){
                    preNode2 = preNode2.next;

                }
                node2 = preNode2.next;
                preNode2.next = cur;

            }
            preNode1 = preNode1.next;
        }
        //退出while，两个链表有一个完事了，如果是第一个，那么第二个需要都添加进来
        if(node2 != null){
            preNode1.next = node2;
        }
        return dummyNode.next;

    }

    //其实没有必要再第一个上面操作，只需要新建一个node即可，倆个node都往这个上面挂就好了，只需要头就行
    //跟数组的归并排序所需要的的空间不一样
    private ListNode merge2(ListNode node1, ListNode node2){
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        while(node1 != null && node2 != null){
            if(node1.val < node2.val){
                cur.next = node1;
                node1 = node1.next;
            }else{
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        if(node1 == null){
            cur.next = node2;
        }
        if(node2 == null){
            cur.next = node1;
        }
        return ret.next;
    }

    //快慢指针找出Mid,找链表的第(倒数第)几个都记得快慢指针
    public ListNode getMid(ListNode start){
        ListNode fast =start,slow = start;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow=slow.next;
        }
        return slow;
    }


    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
//        if(head.next.next == null){
//            if(head.val > head.next.val){
//                dummyNode.next = head.next;
//                head.next = null;
//                dummyNode.next.next = head;
//            }
//            return dummyNode.next;
//        }
        ListNode mid = getMid(head);
        ListNode midNext = mid.next;
        //start->mid   mid.next->end
        //设置min.next = null
        mid.next = null;
        head = sortList(head);
        midNext = sortList(midNext);
        return head.val <= midNext.val ? merge2(head, midNext) : merge2(midNext, head);

    }

    public static void main(String args[]) {
        int[] arr = {2,1,3};
        ListNode head = new ListNode(4);
        ListNode p = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode tmpNode = new ListNode(arr[i]);
            head.next = tmpNode;
            head = head.next;
        }
        ListNode x = new Solution().sortList(p);
        System.out.println(x);
    }
}

